The technique of employing a high speed cache memory between a processor and a main memory to hold a dynamic subset of the information in the main memory in order to speed up system operation is well known in the art. Briefly, the cache holds a dynamically variable collection of main memory information fragments selected and updated such that there is a good chance that the fragments will include instructions and/or data required by the processor in upcoming operations. If there is a cache "hit" on a given operation, the information is available to the processor much faster than if main memory had to be accessed to obtain the same information. Consequently, in many high performance data processing systems, the "cache miss ratio" is one of the major limitations on the system execution rate, and it should therefore be kept as low as possible.
The key to obtaining a low cache miss ratio is obviously one of carefully selecting the information to be placed in the cache from main memory at any given instant. There are several techniques for selecting blocks of instructions for transitory residence in the cache, and the more or less linear use of instructions in programming renders these techniques statistically effective. However, the selection of operand information to be resident in cache memory at a given instant has been much less effective and has been generally limited to transferring one or more contiguous blocks including a cache miss address. This approach only slightly lowers the cache miss ratio and is also an ineffective use of cache capacity.
Thus, those skilled in the art will understand that it would be highly desirable to provide means for selecting operand information for transitory storage in a cache memory in such a manner as to significantly lower the cache miss ratio. That end was accomplished in accordance with the invention disclosed and claimed in U.S. patent application Ser. No. 07/364,943 filed Jun. 12, 1989, for CACHE MISS PREDICTION METHOD AND APPARATUS by Charles P. Ryan, now U.S. Pat. No. 5,093,777, by special purpose apparatus in the cache memory which stores recent cache misses and searches for operand patterns therein. Any detected operand pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss.
However, the method and apparatus disclosed therein had the inherent drawback that the patterns are always searched in the same sequence. If, for example, the pattern found is the last of eight searched, it would always require seven search cycles to find the pattern, a fact which adversely affects the advantage of prefetching the next request. The present invention overcomes this drawback.
Inventions which address other improvements to the invention disclosed and claimed in U.S. Pat. No. 5,093,777 are discussed immediately below for their peripheral relevance to the present invention.
Under certain operating conditions, the full time use of the procedure disclosed and claimed in U.S. Pat. No. 5,093,777 can actually raise the long term miss ratio (i.e., lower the long term hit ratio). In a typical cache based processor that executes a single process during a given period, the cache hit ratio will stabilize after some time interval following the institution of the process. If a change to another process is made, new instructions and data must be loaded into the cache such that cache hit ratio instantaneously drops dramatically and then increases as the new process is "experienced". If the cache miss prediction mechanism is in operation, the initial rate of increase in the cache hit ratio is much faster. However, the hit ratio never reaches the level it would reach in the long term if the cache miss prediction mechanism was not in use. This result is caused by the fact that the cache miss prediction mechanism continues to find and load from main memory the next possible miss which, however, is not used, thus forcing the cache to replace blocks that are more important.
The invention disclosed and claimed in U.S. patent application Ser. No. 07/841,687 filed Feb. 26, 1992, for SELECTIVELY ENABLED CACHE MISS PREDICTION METHOD AND APPARATUS by Charles P. Ryan overcomes the limiting effect of using the cache miss prediction mechanism continuously after a process has been changed by selectively enabling the cache miss prediction mechanism only during cache "in-rush" following a process change to increase the recovery rate; thereafter, it is disabled, based upon timing-out a timer or reaching a hit ratio threshold, in order that normal procedures allow the hit ratio to stabilize at a higher percentage than if the cache miss prediction mechanism were operated continuously.
There are operating conditions, however, under which it would be advantageous to have the cache miss prediction mechanism in operation even after cache inrush following a process change. An example of such an operating condition occurs when very large sets (even in excess of the cache size) of regularly addressed operand data (matrix/vector/strings) are used by a procedure. An invention which takes advantage of this characteristic is disclosed in U.S. patent application Ser. No. 07/850,713 filed Mar. 13, 1992, for CONTROLLING CACHE PREDICTIVE PREFETCHING BASED ON CACHE HIT RATIO TREND (as amended) by Charles P. Ryan, now U.S. Pat. No. 5,367,656. This feature is achieved by special purpose apparatus which stores recent cache misses and searches for address patterns therein. Any detected pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss. The cache miss prediction mechanism is selectively enabled by an adaptive circuit that develops a short term operand cache hit ratio history and responds to ratio improving and ratio deteriorating trends by accordingly enabling and disabling the cache miss prediction mechanism.